package com.leetcode.no121;

import java.util.ArrayDeque;
import java.util.Stack;

public class Solution {
    public int maxProfit(int[] prices) {
        int[] prices2 = new int[prices.length + 1];
        System.arraycopy(prices, 0, prices2, 0, prices.length);
        prices2[prices.length] = -1; //哨兵, 保证所有的元素出栈

        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int ans = 0;
        for (int j : prices2) {
            while (!stack.isEmpty() && stack.peek() >= j) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    continue;
                }
                ans = Math.max(ans, top - stack.peekLast()); // 出栈时栈顶减去栈底元素
            }
            stack.push(j);
        }
        return ans;
    }
}
